/*
 * BiTree.h
 *
 *  Created on: 2011-5-3
 *      Author: william nie
 */

#include "datadef.h"
#include<stdio.h>
#include<stdlib.h>


#ifndef BITREE_H_
#define BITREE_H_

typedef enum {LEFT , RIGHT} LR;

typedef struct BiTreeNode{
	int data;
	struct BiTreeNode *lchild;
	struct BiTreeNode *rchild;
} BTNode;

typedef struct {
	BTNode *root;
	int nodnum;
	int depth;
	int treesize;
} BiTree;

typedef BOOL (*Visit)(BTNode *elem);

Status InitBiTree(BiTree **biTree);

Status DestoryBiTree(BiTree *biTree);

BiTree* CreateBiTree();

Status ClearBiTree(BiTree *biTree);

BOOL BiTreeEmpty(BiTree *biTree);

int BiTreeDepth(BiTree *biTree);

BTNode* Value(BTNode *btNode , int value);

Status Assign(BiTree *biTree , int oldValue , int newValue);

BTNode* Parent(BiTree *biTree , BTNode *elem);

BTNode* LeftChild(BTNode *elem);

BTNode* RightChild(BTNode *elem);

BTNode* LeftSibling(BiTree *biTree, BTNode *elem);

BTNode* RightSibling(BiTree *biTree, BTNode *elem);

Status InsertChild(BiTree *biTree , BTNode *parent , LR pos , BTNode *child);

Status DeleteChild(BiTree *biTree , int parentData , LR pos);

Status PreOrderTraverse(BTNode *btNode , Visit visit);

Status InOrderTraverse(BTNode *btNode , Visit visit);

Status PostOrderTraverse(BTNode *btNode , Visit visit);

Status LevelOrderTraverse(BiTree *biTree , Visit visit);

BOOL DefaultBiVisit(BTNode *elem);

BOOL SearchBiVisit(BTNode *elem , int data);


/*******Queue Helper*******/

typedef BTNode BQElemType;
typedef struct BQNode{
	BQElemType* data;
	struct BQNode*	next;
} BQNode;

typedef struct {
	BQNode* front;
	BQNode* rear;
} BiQueue;

Status InitBiQueue(BiQueue **queue);

Status DestroyBiQueue(BiQueue **queue);

BOOL BiQueueEmpty(BiQueue *queue);

Status EnBiQueue(BiQueue *queue , BQElemType *node);

BQElemType* DeBiQueue(BiQueue *queue);

#endif /* BITREE_H_ */
